/*
  快速排序
  原理：就是寻找分区点，保证分区点左边的元素都小于分区点，右边都大于分区点，一直分区到数组
  的元素个数是0或者1，就不分区了，这样当全部完成的时候就完成了排序
 */

class QuickSort {
  sort(arr) {
    this.quickSort(arr, 0, arr.length - 1);
  }
  quickSort(arr, l, r) {
    if (l >= r) {
      return;
    }
    const partition = this.partition(arr, l, r);
    this.quickSort(arr, l, partition - 1);
    this.quickSort(arr, partition + 1, r);
  }

  swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  partition(arr, l, r) {
    // 随机选取定点，可以解决在数组完成有序的情况下退化成O(n^2)的情况
    let tempPartition = Math.floor(Math.random() * (r - l + 1)) + l;
    this.swap(arr, l, tempPartition);
    let j = l;
    // arr[l+1...j] < v ; arr[j+1...i] >= v
    for (let i = l + 1; i <= r; i++) {
      if (arr[i] < arr[l]) {
        j++;
        // 当小于的时候，j++，然后交换位置，保证[l+1, j]区间 < arr[l]
        this.swap(arr, j, i);
      }
    }
    this.swap(arr, l, j);
    return j;
  }
}
function generateArr(num, end) {
  const arr = [];
  for (let i = 0; i < num; i++) {
    // eslint-disable-next-line no-unused-expressions
    arr[i] = Math.floor(Math.random() * end);
  }
  return arr;
}
const sort = new QuickSort();
const arr = generateArr(20, 100);
console.log(arr);
sort.sort(arr);
console.log(arr);
